package pers.qianyu.month_202102.date_20210215;

import org.junit.*;

/**
 * 300. 最长递增子序列
 * https://leetcode-cn.com/problems/longest-increasing-subsequence/
 * - 二分查找法
 *
 * @author mizzle rain
 * @date 2021-02-15 21:12
 */
public class LengthOfLIS2 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int cnt = 0;
        int[] top = new int[n];
        for (int x : nums) {
            int left = 0, right = cnt;
            while (left < right) {
                int mid = left + right >> 1;
                if (top[mid] >= x) right = mid;
                else left = mid + 1;
            }
            if (left == cnt) cnt++;
            top[left] = x;
        }
        return cnt;
    }

    @Test
    public void test1() {
        int result = new LengthOfLIS2().lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18});
        Assert.assertEquals(4, result);
    }
}
